class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def distanceK(self, root, target, k):
        d = {}

        def search(node, dist):
            if dist >= 0:
                dist += 1
                if node.val not in d:
                    d[node.val] = dist
                else:
                    dist = d[node.val]
                if node.left:
                    search(node.left, dist)
                if node.right:
                    search(node.right, dist)
            else:
                if node == target:
                    d[node.val] = 0
                    if node.left:
                        search(node.left, 0)
                    if node.right:
                        search(node.right, 0)
                    return 0
                else:
                    left_dist = -1
                    right_dist = -1
                    if node.left:
                        left_dist = search(node.left, -1)
                    if node.right:
                        right_dist = search(node.right, -1)
                    out_dist = max(left_dist, right_dist)
                    if out_dist >= 0:
                        out_dist += 1
                        d[node.val] = out_dist
                    return out_dist

        search(root, -1)
        search(root, d[root.val])
        out = []
        for key in d:
            if d[key] == k:
                out.append(key)
        return out